On the Internet, display advertising on web pages appears in the form of web banners known as banner ads. Banners ads can comprise static or animated images, as well as interactive media that may include audio and video elements.
The banner ads shown on some websites are sold by negotiated contract in advance. The impression inventory is diverse, with advertisers looking to meet campaign limits in terms of demographics targets (who an ad is shown to), temporal targets (when an ad is shown), and location targets (where an ad is shown). Any particular advertiser request may be able to be met in a variety of ways.
A seller of advertisements such as banner ads has a complex online optimization task. Advertisers are buyers of advertisements and send requests to buy advertisements from the seller. As advertiser requests to buy banner ads arrive at the seller, the seller decides whether the requests should be accepted or not. This is a complex task to perform with any reasonable quality guarantee when formulated as an online optimization problem. There may be thousands of advertisers on a website. Inventory may be preallocated to advertisers at a low value early. It may not ever be learned that advertisers arriving later would have paid a premium for the same inventory. Absent this knowledge, there is little basis for a seller to accept or decline ad requests placed by advertisers.